The present invention relates to shifters and, more particularly, to an improvement in a shifter which increases its efficiency and allows it to be used to shift two or more distinct data words at once.
Shifters and accumulators are well-known in microcontrollers, microprocessors, and digital signal processors. One use of a shifter is to shift a data string or word a particular shift amount. For purposes of the present discussion, it should be understood that each element of the data string will be referred to as a bit with the serial arrangement of the collection of such bits being referred to as a data string, word or number.
Shifters can support many different types of shift modes including, for example, arithmetic shifting, logical shifting, or barrel shifting. FIGS. 1a-1d illustrate schematically different types of shifts typically performed by a shifter. The shifts in FIGS. 1a-1c can be represented by instructions as follows:
For FIG. 1a: aD=aS&lt;&lt;ar PA1 For FIG. 1b: aD=aS&gt;&gt;ar PA1 For FIG. 1c: aD=aS&gt;&gt;&gt;ar
For the above listed expressions, aS stands for a source accumulator in which a data word is originally stored, aD stands for a destination accumulator where the shifted word or number is stored, and ar stands for an auxiliary register that contains the shift amount. The notations "&lt;&lt;" and "&gt;&gt;" indicate arithmetic shifts left and right, respectively, and the notation "&gt;&gt;&gt;" indicates a logical shift right.
FIGS. 1a-1c show graphically the implementation of these instructions in standard shifting techniques. The device indicated generally as 10 has a source accumulator indicated generally as 12 which is capable of a 32 bit capacity with bits numbered from 0 to 31. The output from the shift falls to the destination accumulator indicated generally as 14. Depending on the type and amount of shift made, the data string in the destination accumulator 14 can vary, with FIGS. 1a-1c illustrating exemplary shifts.
For example, as illustrated in FIG. 1a, an arithmetic shift left occurs in accordance with the first instruction. In so doing, the bits in the source accumulator 12 are shifted leftwardly the specified amount and bits of value 0 are shifted into the destination accumulator starting at bit 0. Conversely, as illustrated in FIGS. 1b and 1c, a shift right instruction causes the data word to be displaced such that the leftmost places in the destination accumulator 14 starting at bit 31 move in the right direction by the designated shift amount. In the case of the arithmetic shift right function of FIG. 1b, the sign bit s stored in bit 31 is shifted into the blank spaces left by the bits shifted right. In a logical shift right instruction as illustrated in FIG. 1c, the shifting of the data string or number is done similarly except that the open or blank spaces otherwise occupied by the data number (namely, bit 31 moving rightwardly therefrom the shift amount) receive a value of 0. A logical shift left produces the same result as in the arithmetic shift left shown in FIG. 1a.
A right barrel shift is illustrated in FIG. 1d. In a barrel shift, the bits 15a shifted out of the data word at the right or lower end are shifted into the open spaces 15b at the left or upper end of the word.
A shifter for implementing the shifts described above is shown in FIG. 2. FIG. 2 illustrates a standard cascaded multiplexer identified generally as 16 which connects a 32 bit length source accumulator 20 with bit places 0 through 31 (including lower half 0 through 15 and upper half 16 through 31) and a 32 bit length destination accumulator 24 with bit places 0 through 15 and 16 through 31. The cascaded multiplexer 16 includes a plurality of multiplexers or multiplexer stages 18 . . . 18"". The data word from the source accumulator 20 is input to the first multiplexer stage 18 which is capable of causing a 16 bit shift right or left or no shift at all. The single data string output from the last multiplexer stage 18"" is input to the destination accumulator 24. The shifted data word could have as few as a single informational bit from the original data word (excluding logic or sign extend elements), depending on how many shifts occur at each stage.
Several user settable controls control the operation of the shifter. An auxiliary register 30 contains the shift amount for the entire shift. Each bit in the auxilary register 30 controls whether a given stage involved in the shift is performed. A left/right control 32 controls the direction of the shift. A sign extend control 34 controls whether the sign bit is extended in a right shift or whether 0's are shifted into the open bit spaces.
The operation of the standard cascaded multiplexer 16 involves the first multiplexer 18 producing a 16 bit left, a 16 bit right or an unshifted version of the single number received from the source accumulator 20. The next stage 18' receives bits 26 output by the prior stage 18 and produces an 8 bit left, 8 bit right or unshifted version of the output of the previous stage. This process continues through successive stages 18" . . . 18"" until the shifted number is output to the destination accumulator 24 in the desired shifted form as determined by the logic set in the auxiliary register 30. The m bit in the auxiliary register[m] controls whether or not a shift of 2.sup.m bits occurs at each stage, and the left/right control 32 controls the direction of shift. That is, the cascaded logic in the auxiliary register 30 produces a shift amount equivalent to the encoded values of ar[4] ar[3] ar[2] ar[1] ar[0] and the 32 bit data word is shifted as a whole by that amount.
In the prior art shifter shown in FIG. 2, the lower bit shift left inputs, locations 0-15. of each stage are tied to 0 while the upper shift right inputs, locations 16-31, include additional multiplexing to support sign or zero extending. Each bit location or splice in each multiplexer stage receives several inputs from the prior stage and selects among those inputs based on the controls 30, 32, and 34. For example, FIGS. 2a-2c depict exemplary bit splices of the shift 2 stage 18'". As shown in FIG. 2a, the bit splice for the 31 bit, a.sub.31, receives the following four inputs from the prior stage 18", which are selected based upon the controls as follows: a.sub.31 (selected for a shift right with sign extend), 0 (selected for a shift right without sign extend), a.sub.31 (selected for no shift), and a.sub.29 (selected for shift left). Similarly, FIG. 2b shows a bit splice for the a.sub.29 bit, with inputs from the prior stage of the a.sub.31 and a.sub.27 bits for shifts right and left, respectively, and the a.sub.29 bit for no shift. Finally, FIG. 2c illustrates the a.sub.0 bit splice of the 2 shift stage 18'", which selects from inputs of the a.sub.2 bit for a right shift, the a.sub.0 bit for no shift, and 0 for a shift left.
As a result, the multiplexers 18 . . . 18"" in shifter 16 can effectively shift a data word contained in the source accunulator into a shifted data word output to the destination accumulator 24.
However, such cascaded multiplexers as shown in FIG. 2 are limited to the shifting of a single data string or word which occupies the full 32 bit source accumulator. In many applications, this becomes an inefficient way of utilizing the microcomputer. Many signal processing applications require reduced precision such as 16-bit precision, and the use of a 32 bit shifter to shift a 16-bit data string or word is inefficient and leaves the shifter underutilized. Indeed, the need to shift two 16-bit words would require the use of two 32 bit shifters, thus requiring additional resources and time to perform the operations. This problem becomes more pronounced when the disparity between shifter length and word length increases.
There is thus a need to reduce or eliminate the wasted capacity in existing shifters.